The use of computers and computer networks is now almost pervasive in industrialized countries. Hardly a business exists that does not rely on computers and software either directly or indirectly, in their daily operations. As well, with the expansion of powerful communication networks such as the Internet, the ease with which computer software and data may be accessed, exchanged, copied and distributed is also growing daily. With this growth of computing power and communication networks, it is more critical than ever to control access to these resources, preventing unwanted parties from accessing confidential software and data.
Access to computer systems is often protected by a password consisting of a single word, or a pass phrase consisting of a string of words or characters. A pass phrase has the advantage over shorter passwords in that it can have sufficient information content to permit its conversion into a secure cryptographic key by the use of a cryptographically strong hash function. A cryptographically strong hash function generates what appears to be a random number from a given input, however, a given input will only generate one specific output. On the other hand, cryptographically strong hash functions are “non-reversible” in that given the function and a product of the function, an impractically large degree of processing must be performed to determine the value of the operand (testing all combinations for a 64-bit hash code, for example, would require 500 million years, at a rate of 100 million tests per second). Such functions are well known in the art, and include MD5 from RSA and the SHA algorithm from NIST.
Access control via passwords and pass phrases is part of a broader subject of “authentication”. Authentication is basically the verification of one party's identification to another party. These parties may be individuals, software or hardware. A user may, for example, have to authenticate to a piece of local software to operate a software package or access a stored data file, authenticate to a local server in an office environment, or authenticate to a remote server over the Internet, in an e-commerce environment. The parties to which the user authenticates are referred to as authenticators. The user may be considered the authenticatee, or he may use a piece of software which performs the authentication on his behalf.
When a user employs a high-quality password or pass phrase (that is, one resistant to cracking), avoids recording it where a hostile person might find it, and succeeds in remembering it, the password or pass phrase provides convenient and secure access to the resources which it protects.
However, there are significant difficulties with the use of passwords or pass phrases:    1. Passwords or pass phrases which are resistant to brute-force cracking (such as a “dictionary attack” where access attempts are made by randomly selecting words from a dictionary) are difficult for their users to remember reliably, especially if periods of use are interspersed with periods during which they are unused, such as vacations.            This results in calls to support staff for the recovery or replacement of forgotten passwords or pass phrases, which can be a significant operating cost.        Moreover, the provision of new passwords or pass phrases by such support staff is itself a significant security risk. (Why crack a password when you can have one given to you by employing a little acting talent?)            2. Passwords or pass phrases which are easy to remember are typically easier to crack because the user generally employs data he is already familiar with such as birth dates of family members, postal addresses and telephone numbers. These passwords can often be determined by a little searching plus some applied detective work.    3. A password or pass phrase generally applies to a unique resource, so that the problems with passwords are exacerbated by the need for a user to have several of them, one per resource.            If their security could be improved while avoiding the normal overhead incurred for replacement of forgotten, lost, or compromised high-quality passwords or pass phrases, a single point of access could be applied securely to more than one resource.        
In their paper, Protecting Secret Keys with Personal Entropy (available on the Internet at http://www.counterpane.com/personal-entropy.html), Carl Ellison, Chris Hall, Randy Milbert, and Bruce Schneier propose replacing a single, high-quality pass phrase with a series of simpler pass phrases which may be of lower quality individually, but are of sufficient quality considered together. The user is prompted to respond to a series of questions or hints, each response being one of these simpler pass phrases.
In order to deal with the problem of forgetting, they propose a fault-tolerant usage for these simpler pass phrases. That is, the user is only required to provide correct answers to a predetermined proportion of the questions (t out of n).
The method of Ellison et al. is presented in the flow diagrams of FIGS. 1 and 2. An explanation of the notation used in FIGS. 1 and 2 is presented in FIGS. 10A through 10C.
The setup procedure 10 for the Ellison method is presented in FIG. 1. As preparation for this procedure, a set of data 12 has been generated including:                an array of n questions, q1 . . . qn;        an array of n corresponding answers, a1 . . . an;        a random ‘salt’ value, rs; and        a high-quality cryptographic key, s.        
The questions q1 . . . qn and answers a1 . . . an draw upon the authenticatee's (i.e. the user's) personal history and are established as part of an initialization routine. Generally, the initialization routine would pose questions having answers which would be obscure and very difficult for an attacker to determine, yet would be relatively easy for the user to remember, such as “what was the first car you drove?” or “what was the name of your first pet?” Ellison et al. provide much valuable advice on choosing good questions for this purpose.
The random ‘salt’ value, rs, is simply a random number which could be generated by the setup routine, which is used to add further randomness into a hashing function in the routine. The high-quality cryptographic key, s, is the password which the user will employ to obtain access on a day-to-day basis.
As shown in FIG. 1, the cryptographic key, s, is split into n shares, s1 . . . Sn, using an n, t threshold sharing method 14. This is an operation where n new values are produced from one value, in such a way that only t of them (t<n) are needed to recover the one original value (see also block 230 in FIG. 10C). A technique for doing this which is known in the art is Shamir's method of using Lagrange polynomials. This sharing provides the basis for the fault tolerance of this method, which is described in greater detail hereinafter.
Note that the flow of the cryptographic key, s, to the splitting function 14 is represented by a thin line, which indicates a data path for a single value (per 238 of FIG. 10C). This is in contrast to the thicker lines which represent a data path for multiple values (per 236 of FIG. 10C).
Next, a cryptographic key, ki is generated for each corresponding pair of questions and answers, (qi, ai) by performing a hashing function 16 on the (qi, ai) pair and the random ‘salt’ value, rs (see also block 240 in FIG. 10C). These cryptographic keys, k1 . . . kn, are used to encrypt 18 each corresponding share, si, of the user's high-quality cryptographic key, s, yielding a corresponding crypto-share, ci, (see block 210 in FIG. 10A for an explanation of how encryption functions are presented in the figures).
The array of questions, q1 . . . qn, the random ‘salt’ value, rs, and the crypto-shares, c1 . . . Cn, are then stored 20 by the authenticator for later use, completing the setup procedure. Note that the authenticatee's answers have now been hashed and encrypted into a set of crypto-shares, c1 . . . Cn, which cannot be easily reversed to yield the reference answers, a1 . . . an. Thus, if these data were obtained by an attacker, he could not easily determine the original answers.
Under normal operation, the user may now access the secure server or software by supplying his high-quality cryptographic key, s, in response to a challenge. The authenticator simply compares the supplied cryptographic key to a stored copy of the original key, and grants access if they match. If this key is lost, compromised, or forgotten by the user, he will then have to initiate the access procedure 30 presented in FIG. 2.
The access procedure 30 begins by retrieving the previously stored array 32 of questions, q1 . . . qn, the random ‘salt’ value, rs, and the crypto-shares, c1 . . . cn. The access routine will then challenge the user to provide answers to the array of questions, q1 . . . qn, storing the user's responses as a new set 34 of answers, a′1 . . . a′n. Note that these answers, a′1 . . . a′n may or may not match the reference answers, a1 . . . an.
The access routine then computes a cryptographic key, k′i, by performing a hash 36 for each question-answer pair, qi and a′i, using the stored random ‘salt’ value, rs. Each cryptographic key, k′i, is then used to decrypt 38 the corresponding crypto-share, ci, yielding a new share, s′i, (see block 212 in FIG. 10A for an explanation of how decryption functions are presented in the figures).
The fault-tolerant aspect of the Ellison method is now performed: an exhaustive search 40 for a subset of t out of the n shares is made until either all possible combinations have been exhausted without success, or a subset is found which permits the retrieval of s, the high-quality cryptographic key (see also block 234 in FIG. 10C). The fault-tolerant aspect of this approach is that it permits access if up to (n−t) of the questions are answered incorrectly. That is, the user is only required to provide correct answers to a predetermined number t, of the n questions.
The method presented by Ellison et al. has a number of problems which limit the degree of protection it offers, and hence, limit its usefulness. For example:    1. because the random ‘salt’ value, rs, is stored and processed in an unprotected form with both the authentication and authenticatee, it could be located and used by an attacker;    2. for the cryptographic key, s, to be strong, it must be a long, nonsensical, string of characters. This would make it extremely difficult for the user to remember, but none of the alternatives is effective:            a. writing the cryptographic key, s, down on paper, makes it vulnerable to discovery in a physical search;        b. storing it on the local system, makes it vulnerable to discovery via an electronic search or attack; and        c. retrieving it every time it is required by answering a series of questions, is a slow and effortful activity;            3. during retrieval, the answer to each question must be precisely correct. Thus, this method will not work for biometric data, for example;    4. because the attacker only has to get t of n answers correct, he, in effect, is allowed to choose which answers he can correctly determine;    5. the output of this technique is to retrieve the old key, which is not always the best strategy.
There is therefore a need for a password recovery system which is more practical for general day more to day use, and is more secure against attack.